1. Field of the Invention
The present invention relates to a method and an apparatus for processing image data for sequentially filling inner regions of grahic and font characters and figures approximated by polygons with a black dot along scanning lines.
2. Description of the Prior Art
Image data processing of sequentially filling inner regions of characters and figures along scanning lines thereby to record or display the characters and figures is well known in the art in the name of "raster scanning". In such raster scanning, the characters and figures are approximated by polygons, inner regions of which are sequentially filled.
Such filling has been performed in the prior art in such a manner that image data of closed curves obtained from polygons are written in memory having storage areas in one-to-one correspondence to pixels of images to be recorded, and, after that, scanning for filling is performed in four vertical and horizontal four directions from a reference point which is set in an arbitrary position in each one of the closed curves.
In such a method, however, the time required for filling operation is increased in an apparatus such as a process scanner which records figures along scanning lines. furthermore, in the case of outputting an image having a relatively large numbers of pixels, a memory having a large storage capacity is required.
In order to overcome the problems, the following method is employed for recording an image formed by a number of pixels. When, for example, a pentagon as shown in FIG. 1 is transformed to raster image data, intersection points of segments formed by sequentially connecting respective vertices of the pentagon and the scanning lines are obtained by a CPU through linear interpolation, on the basis of coordinate values of the vertices (X.sub.1, Y.sub.1), (X.sub.2, Y.sub.2), . . . (X.sub.5, Y.sub.5). For example, Y coordinates Y.sub.n corresponding to X coordinates X.sub.n between the apexes (X.sub.1, Y.sub.1) and (X.sub.2, Y.sub.2) of the pentagon as shown in FIG. 1 are obtained as follows: ##EQU1##
Then, as shown in FIG. 2, "raster start points" and "raster end points" are obtained as the intersection points of the scanning lines and the segments. In these points, "raster start points" are defined as the intersection points at which a scanning line enters from the outer region to the inner region of the figure. On the other hand, "raster end points" are defined as the intersection points at which a scanning line goes out from the inner region to the outer region of the figure. These data are registered per scanning line in a RAM, to be sequentially read from the RAM thereby to obtain raster image data as required.
More concretely, in a circuit as shown in FIG. 3, date "0" are written in all addresses of a RAM 12 in which one bit is assigned per pixel and having capacity for over one scanning line. After that, data "1" are written in addresses corresponding to the raster start and end points in a random access manner. Then an address selector 5 is switched from a random address mode to a sequential address mode to input read data S.sub.b read from the RAM 12 and clock signals S.sub.a synchronous with reading signals of the RAM 12 in an output data generator 13, which is shown in FIG. 4 in detail, thereby to obtain raster image signals S.sub.c as shown in FIG. 5.
In this method, however, another problem is caused in the case of outputting a figure formed by overlapping a plurality of unit figures, e.g., a nonagon indicated as ABCDEFGHI formed by overlapping two triangles .DELTA.AEF and .DELTA.HCJ, as shown in FIG. 14.
Namely, in this case, the coordinates of intersection points (B), (D), (G) and (I) must be also calculated for obtaining the contour of the nonagon. Thus, the time required for calculating intersection points of figures cannot be disregarded when the figures are complicated in configuration or a large number of unit figures are overlapped. This is because the processing time required for arithmetic is considerably increased in this method since, with respect to the relation of raster start and end points of the respective polygons, the raster start points may be changed to the raster end points or mere passage points etc.
Further, the raster start and end points may be doubled at the single vertex depending on intersection modes of the horizontal scanning lines and the polygons. In this case, the vertex must be treated as the raster start point while providing another end point adjacent to the start point. Therefore, the figure cannot be correctly reproduced at the start and end points.